package demon1;

public class BinarySerachTree {
    public  static class Node{
        int val;
        Node left;
        Node right;
        public Node(int val){
            this.val=val;
        }
    }
    Node root=null;
    public Node search(int val){
        Node cur=root;
        if(root==null){
            return null;
        }
        while(cur!=null){
            if(cur.val==val){
                return cur;
            }
            if(val<cur.val){
                cur=cur.left;
            }else{
                cur=cur.right;
            }
        }
        return null;
    }
    public boolean insert(int val){
        Node node =new Node(val);
        if(root==null){
            root=node;
        }
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }else if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }
            if(cur.val==val){
                return false;
            }
        }
        if(parent.val<val){
            parent.right=node;
        }else{
            parent.left=node;
        }
        return true;
    }
    public void removeNode(int val){
        if(root==null){
            return;
        }
        Node cur=root;
        Node parent=null;
        while(cur!=null){
            if(cur.val==val){
                remove(cur,parent);
            }
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
    }
    public void remove(Node cur,Node parent){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(cur.val<parent.val){
                parent.left=cur.right;
            }else{
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur.val<parent.val){
                parent.left=cur.left;
            }else{
                parent.right=cur.left;
            }
        }else{
            //这里是替换删除,不是真正意义上的删除.
            Node tagetP=cur;
            Node taget=cur.right;
            while(taget!=null){
                tagetP=taget;
                taget=taget.left;
            }
            cur.val=taget.val;
            if(taget== tagetP.left){
                tagetP.left=taget.right;
            }else{
                tagetP.right=cur.right;
            }

        }
    }
}

